from typing import *


class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        coins.sort()
        s, ans, j = 0, 0, 0
        for i in range(1, target + 1):
            if i > s:
                if j == len(coins) or i - coins[j] < 0:
                    ans += 1
                    s += i
                else:
                    s += coins[j]
                    j += 1
        return ans
